题面

即用半径为 $2$ 的圆覆盖一棵树的最少圆个数

解题思路

树形 $DP$ $/$ 神仙贪心

分析

一个点的状态比较少，因此可以 食 用动态规划

但是状态并不是只有选这个点和不选这个点两种，因为半径变大之后

状态就会复杂一点，变成：

设该点为 $k$，则

1、选 $k$ 这个点

2、不选 $k$，但 $k$ 距其子树中被选结点的最短距离为 $1$

3、不选 $k$，但 $k$ 距其子树中被选结点的最短距离为 $2$

4、不选 $k$，但 $k$ 距其子树中被选结点的最短距离为 $3$

5、不选 $k$，但 $k$ 距其子树中被选结点的最短距离为 $4$

也就是分五种情况讨论

f[k][0]: 选该点的最小花费
f[k][1]: 该点距其子树中被选结点的最短距离为1的最小花费
f[k][2]: 该点距其子树中被选结点的最短距离为2的最小花费
f[k][3]: 该点距其子树中被选结点的最短距离为3的最小花费
f[k][4]: 该点距其子树中被选结点的最短距离为4的最小花费

显然，（$to$ 为 $k$ 的子结点）

1、f[k][0] 至 f[k][4] 所需满足的条件越来越少，也就是说，f[k][i-1] 的值可以更新 f[k][i],i belong to {1,2,3,4}

2、f[k][3] 和 f[k][4] 分别可以由其子结点的 f[to][2] 和 f[to][3] 直接更新

3、f[k][0] 可以由 f[to][4] 直接更新

这样之后，我们再讨论下 f[k][1] 和 f[k][2] 的情况即可

f[k][1] 由 f[to][0] 转移而来，显然只需要一个子结点能覆盖到即可，也就是说可以枚举每个 $to$ ，然后用 f[to][0] + 其他子结点的 f[_][3] 更新答案

f[k][2] 由 f[to][1] 转移而来，同理，可以枚举每个子结点，然后 f[to][1] + 其他子结点的 f[_][2] 更新答案

转移代码：

inline void dfs(rint k) {
    rint i,to,sum=0,res=0;f[k][1]=f[k][2]=inf;
    for(i=head[k];i;i=nxt[i]) {
        to=ver[i],dfs(to);
        if(f[k][0]<inf) f[k][0]+=f[to][4];
        if(sum<inf) sum+=f[to][2];
        if(res<inf) res+=f[to][3];
        if(f[k][3]<inf) f[k][3]+=f[to][2];
        if(f[k][4]<inf) f[k][4]+=f[to][3];
    }
    for(i=head[k];i;i=nxt[i]) {
        to=ver[i];
        if(f[to][3]<inf) cmin(f[k][1],res-f[to][3]+f[to][0]);
        if(f[to][2]<inf) cmin(f[k][2],sum-f[to][2]+f[to][1]);
    }
    for(i=1;i<5;i++) cmin(f[k][i],f[k][i-1]);
}

warning

1、间接计算的状态要赋初值为 inf

2、如果累加的时候大于 inf，应停止更新，因为这种情况必定不满足

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rLL rgt LL
#define inf 0x3f3f3f3f
#define N 1003
using namespace std;
template<class K>inline bool cmax(K&a,const K b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K b){return(a>b)?a=b,1:0;}
int n,t,ver[N],nxt[N],head[N],f[N][5];
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
inline void add(rint x,rint y) {
    ver[++t]=y,nxt[t]=head[x],head[x]=t;
}
inline void dfs(rint k) {
    rint i,to,sum=0,res=0;f[k][1]=f[k][2]=inf;//注意两种间接计算的状态要计算初值
    for(i=head[k];i;i=nxt[i]) {
        to=ver[i],dfs(to);
        if(f[k][0]<inf) f[k][0]+=f[to][4];
        if(sum<inf) sum+=f[to][2];
        if(res<inf) res+=f[to][3];//处理总和间接转移
        if(f[k][3]<inf) f[k][3]+=f[to][2];
        if(f[k][4]<inf) f[k][4]+=f[to][3];//直接转移
    }
    for(i=head[k];i;i=nxt[i]) {
        to=ver[i];
        if(f[to][3]<inf) cmin(f[k][1],res-f[to][3]+f[to][0]);
        if(f[to][2]<inf) cmin(f[k][2],sum-f[to][2]+f[to][1]);//间接转移
    }
    for(i=1;i<5;i++) cmin(f[k][i],f[k][i-1]);//更新
}
int main()
{
    rint i;n=read();
    for(i=2;i<=n;i++) add(read(),i);
    dfs(1),printf("%d\n",f[1][2]);
    return 0;
}

另一种解法

神仙贪心，Link

先将整棵树的结点按深度排序，记录一个 o[_] 表示到最近能被覆盖的点的距离

然后如果这个点超出了范围，也就是 o[_]>2 那么在选择这个点，改变其 一到四 辈祖先的 o[_] 值即可

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 2020
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int n,b[N],f[N],d[N],o[N],ans,u,v,w;
bool cmp(int x,int y){return d[x]>d[y];}
int main(){
    scanf("%d",&n);b[1]=1,o[1]=o[0]=N;
    FOR(i,2,n) scanf("%d",&f[i]),d[i]=d[f[i]]+1,b[i]=i,o[i]=N;
    sort(b+1,b+n+1,cmp);
    FOR(i,1,n){
        v=b[i],w=f[v],u=f[f[v]];
        o[v]=min(o[v],min(o[w]+1,o[u]+2));
        if(o[v]>2){
            o[u]=0,ans++;
            o[f[u]]=min(o[f[u]],1),o[f[f[u]]]=min(o[f[f[u]]],2);
        }
    }printf("%d",ans);
}

devil.